﻿// 0824train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <limits>
#include <map>
#include <set>
#include <queue>

using namespace std;

/*
 给定两个字符串 s1 和 s2 和正整数 k，其中 s1 长度为 n1，s2 长度为 n2。
在 s2 中选一个子串，若满足下面条件，则称 s2 以长度 k 冗余覆盖 s1
该子串长度为 n1 + k
该子串中包含 s1 中全部字母
该子串每个字母出现次数不小于 s1 中对应的字母
给定 s1，s2，k，求最左侧的 s2 以长度 k 冗余覆盖 s1 的子串的首个元素的下标，如果没有返回-1。

举例：
s1 = “ab”
s2 = “aabcd”
k = 1
则子串 “aab” 和 “abc” 均满足此条件，由于 “aab” 在 “abc” 的左侧，“aab” 的第一个元素下部为 0，因此输出 0

输入描述

输入三行，第一行为 s1，第二行为 s2，第三行为 k

s1 和 s2 只包含小写字母
输出描述

最左侧的 s2 以长度 k 冗余覆盖 s1 的子串首个元素下标，如果没有返回 -1。

输入
ab
aabcd
1
输出
0
 */
class Solution01
{
public:
    bool check_verify(string& cover_str, int old_left_i, int new_right_i)
    {
        //分析往右移动的过程 1去掉了old_left 2新增了new_right
        char old_left = cover_str[old_left_i];
        if (target_map.find(old_left) != target_map.end())
        {
            //还原
            target_map[old_left] += 1;
            if (target_map.at(old_left)>0)
            {
                remain_count += 1;
            }
        }
        char new_right = cover_str[new_right_i];
        if (target_map.count(new_right) > 0)
        {
            target_map[new_right] -= 1;
            if (target_map[new_right]>=0)
            {
                remain_count -= 1;
            }
            
        }
        if (remain_count ==0)
        {
            return true;
        }
        return false;
    }

    void solve01(string&sub_str, string&cover_str, int length)
    {
        //新子串长度n1 + k
        //如果达不到长度要求，去除
        if (cover_str.size()<sub_str.size()+length)
        {
            cout << -1;
            return;
        }

        int new_sub_size = sub_str.size() + length;
        //待寻找目标字符的数量
        remain_count = sub_str.size();
        int first_left = 0, first_right = new_sub_size - 1;

        //根据目标子串，生成target_map
        for (auto&oh_char:sub_str)
        {
            target_map[oh_char] += 1;
        }

        //检验left=0的子串是否合格
        string first_sub_str = cover_str.substr(first_left, new_sub_size);
        for (auto&oh_char:first_sub_str)
        {
            if (target_map.find(oh_char)!=target_map.end())
            {
                target_map[oh_char] -= 1;
                if (target_map.at(oh_char) >= 0)
                {
                    remain_count -= 1;
                }
            }

        }
        if (remain_count == 0)
        {
            cout << first_left;
            return;
        }

        int old_left = first_left;
        for (int left=1, right=new_sub_size; right<cover_str.size(); left++, right++)
        {
            bool is_find = check_verify(cover_str, old_left, right);
            if (is_find)
            {
                cout << left;
                return;
            }
            old_left = left;
        }
        cout << -1;
    }

private:
    unordered_map<char, int>target_map;
    int remain_count = 0; //sub_str.size()
};


/*
  头和结尾都是元音字母（aeiouAEIOU）的字符串为元音字符串，
  其中混杂的非元音字母数量为其瑕疵度。
  比如:
- "a"，"aa"是元音字符串，其瑕疵度都为 0
- "aiur"不是元音字符串（结尾不是元音字符）
- "abira"是元音字符串，其瑕疵度为 2
给定一个字符串，请找出指定瑕疵度的最长元音字符子串，并输出其长度，
如果找不到满足条件的元音字符子串，输出 0
子串：字符串中任意个连续的字符组成的子序列称为该字符串的子串

输入描述
首行输入是一个整数，表示预期的瑕疵度flaw，取值范围[0, 65535]
接下来一行是一个仅由字符a-z和A-Z组成的字符串，字符串长度(0, 65535]
输出描述
输出为一个整数，代表满足条件的元音字符子串的长度。

输入
0
asdbuiodevauufgh
输出
3
 */

class Solution02
{
public:
    bool checkChar(char oh_char)
    {
        if (target_set.count(oh_char) == 0)
            return true;

        return false;
    }
    
    bool IsTarget(string& sub_str)
    {
        if (sub_str.size() == 0) return false;
        //头和结尾都是元音字母
        bool is_head = target_set.count(sub_str[0]) > 0;
        char tail_char = sub_str[sub_str.size() - 1];
        bool is_tail = target_set.count(tail_char) > 0;

        if (curr_count_==target_length_ && is_head && is_tail)
        {
            return true;
        }
        return false;
    }

    void solve02(string&origin_str, int length)
    {
        target_length_ = length;
        string target_str = "aeiouAEIOU";
        for (auto&oh_char:target_str)
        {
            target_set.insert(oh_char);
        }

        int left_index = 0;
        for (int right_index=0; right_index<origin_str.size(); right_index++)
        {
            char curr_right_char = origin_str[right_index];
            if (checkChar(curr_right_char))
            {
                curr_count_ += 1;
            }

            while (curr_count_>target_length_ && left_index<=right_index)
            {
                char curr_left_char = origin_str[left_index];
                if (checkChar(curr_left_char))
                {
                    curr_count_ -= 1;
                }
                left_index++;
            }

            string sub_str = origin_str.substr(left_index, right_index-left_index + 1);
            bool is_find = IsTarget(sub_str);
            if (is_find)
            {
                int sub_size = sub_str.size();
                result = max(result, sub_size);
            }

        }

        cout << result;
        //solve02-----
    }
private:
    unordered_set<char>target_set;
    int target_length_ = 0;
    int curr_count_ = 0;
    int result = 0;
};

/*
 给你字符串 s 和整数 k 
请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。
英文中的 元音字母 为（a, e, i, o, u）
 
示例 1：
输入：s = "abciiidef", k = 3
输出：3
解释：子字符串 "iii" 包含 3 个元音字母。
 */
class Solution03 {
public:
    bool checkChar(char oh_char)
    {
        return target_set.count(oh_char) > 0;
    }
    int maxVowels(string s, int k) {
        string origin_s = s;
        int sub_size = k;

        string vowel_str = "aeiou";
        for (auto&oh_char:vowel_str)
        {
            target_set.insert(oh_char);
        }

        int first_left_index = 0, first_right_index = sub_size - 1;
        string first_sub_str = origin_s.substr(first_left_index, sub_size);
        for (auto&oh_char: first_sub_str)
        {
            if (checkChar(oh_char))
            {
                curr_count_ += 1;
            }
        }
        result = max(result, curr_count_);
        int old_left_i = first_left_index;

        for (int left_i=1,right_i=sub_size; right_i<origin_s.size(); left_i++,right_i++)
        {
            //丢弃old_left_i
            if (checkChar(origin_s[old_left_i])) curr_count_ -= 1;
            if (checkChar(origin_s[right_i])) curr_count_ += 1;

            result = max(result, curr_count_);
            old_left_i = left_i;
        }
        return result;
    }
private:
    unordered_set<char>target_set;
    int curr_count_ = 0;
    int result = 0;
};



/*
 给定一个连续不包含空格字符串，该字符串仅包含英文小写字母及英文文标点符号（逗号、分号、句号），
 同时给定词库，对该字符串进行精确分词。
说明：

精确分词: 字符串分词后，不会出现重叠。即"ilovechina"，
不同词库可分割为"i, love, china"，“ilove, china”，
不能分割出现重叠的"i, ilove, china"，i重叠出现
标点符号不成词，仅用于断句
词库：根据外部知识库统计出来的常用词汇例：
dictionary=[“i”, “love”, “china”, “lovechina”, “ilove”]

分词原则：采用分词顺序优先且最长匹配原则
譬如：
“ilovechina”，假设分词结果[i, ilove, lo, love, ch, china, lovechina]
则输出 [ilove, china]

错误输出：[i, lovechina]
原因："ilove"优先于"lovechina"成词

错误输出：[i, love, china]
原因:“ilove”>"i"遵循最长匹配原则

输入描述
字符串长度限制：0<length<256
词库长度限制: 1<length<100000
第一行输入待分词语句
第二行输入中文词库

输出描述
按顺序输出分词结果

输入
ilovechina
i,love,china,ch,na,ve,lo,this,is,the,word
输出
i,love,china

 */

class Solution04
{
public:
    bool checkVerify(string&verify_str, string&origin_str)
    {
        int start = curr_index_;
        for (int i=0; i<verify_str.size(); i++)
        {
            if (start==origin_str.size())
            {
                return false;
            }

            if (start<origin_str.size())
            {
                if (origin_str[start] != verify_str[i])
                {
                    return false;
                }
                start += 1;
            }

        }
        return true;
    }
    void solve04(vector<string>&origin_vec, vector<string>&str_vec)
    {
        //index先指向0
        //sort数组，最长的排最前，优先放进去匹配
    	//匹配规则，先匹第一个字母，第一个字母符合，再丢进去整个匹配
        //匹配到了，塞数组里
        //“ilovechina”，假设分词结果[i, ilove, lo, love, ch, china, lovechina]
    	//则输出[ilove, china]
        sort(str_vec.begin(), str_vec.end(),[](string&a, string&b)
        {
                return a.size() > b.size();
        });

        for (auto&origin_str:origin_vec)
        {
            curr_index_ = 0;
            while (curr_index_ < origin_str.size())
            {
                bool is_match = false;
                for (int i = 0; i < str_vec.size(); i++)
                {
                    is_match = checkVerify(str_vec[i], origin_str);
                    if (is_match)
                    {
                        result_vec.push_back(str_vec[i]);
                        curr_index_ += str_vec[i].size();
                        break;
                    }
                }
                if (!is_match)
                {
                    string curr;
                    curr += origin_str[curr_index_];
                    result_vec.push_back(curr);
                    curr_index_ += 1;
                }
            }
        }

        for (int i=0; i<result_vec.size(); i++)
        {
            cout << result_vec[i];
            if (i!=result_vec.size()-1)
            {
                cout << ',';
            }
        }

        //solve04------
    }
private:
    int curr_index_ = 0;
    vector<string>result_vec;
};


int main()
{
    /*
ilovechina.thewordisbeautiful
i,love,china,ch,na,ve,lo,this,is,the,word,beauti,tiful,ful
     */
	{
        string origin_str, total_str;
        cin >> origin_str >> total_str;

        for (auto&oh_char:origin_str)
        {
	        if (oh_char==',' || oh_char==';' || oh_char=='.')
	        {
                oh_char = ' ';
	        }
        }

        vector<string>origin_vec;
        string token;
        stringstream oh_sstream1(origin_str);

        while (oh_sstream1>>token)
        {
            origin_vec.push_back(token);
        }
        
        vector<string>str_vec;
        //string total_str="i,love,china,ch,na,ve,lo,this,is,the,word,beauti,tiful,ful";
        stringstream oh_sstream2(total_str);
        while (getline(oh_sstream2,token,','))
        {
            str_vec.push_back(token);
        }
        Solution04 solu;
        solu.solve04(origin_vec, str_vec);
        //string verify_str = "love";
        //cout << solu.checkVerify(verify_str, origin_str);

        return 0;
	}
	{
        string s = "abciiidef";
        int k = 3;
        Solution03 solu;
        cout << solu.maxVowels(s, k);

        return 0;
	}
	{
/*
0
asdbuiodevauufgh
2
aeueo
*/
        int length = 2;
        string origin_str = "aeueo";
        //int length;
        //cin >> length;
        //string origin_str;
        //cin >> origin_str;

        Solution02 solu;
        solu.solve02(origin_str, length);

        return 0;
	}
/*
ab
aabcd
1
*/
    string sub_str = "ab", cover_str = "ccaaabcd";
    int length = 1;
    //string sub_str, cover_str;
    //cin >> sub_str >> cover_str;
    //int length;
    //cin >> length;

    Solution01 solu;
    solu.solve01(sub_str, cover_str, length);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
